The invention relates to a synchronous data-stream generator for generating a stream of output data items of at least one bit in synchronisation with a clock trigger; the data-stream generator comprising:
a plurality of subgenerators Mi, ixe2x89xa71, each subgenerator Mi comprising a respective clock input and a respective output; each subgenerator Mi being operative to generate a data item of at least one bit on the respective output in response to a trigger received via the respective clock input;
means for combining a generated data item of each of the subgenerators Mi, forming the output data item of the data-stream generator;
a control subgenerator C comprising an input for receiving the clock trigger and an output; the control subgenerator C being operative to generate a control data item of at least one bit on the output in response to the clock trigger; and
control means operative to provide a trigger to at least one of the clock inputs of the subgenerators Mi in dependence on the control data item of the control subgenerator C.
The invention further relates to an encryptor and/or decryptor station comprising the synchronous data-stream generator. The invention also relates to an apparatus comprising a decryptor station comprising the synchronous data-stream generator.
The invention further relates to a method for generating an output stream of data items, each of at least one bit in synchronisation with a clock trigger; the method comprises:
generating a control stream of control data items, each of at least one bit, in synchronisation with the clock trigger; and
generating a plurality of data streams DSi of data items, each of at least one bit; each data stream DSi being generated according to a respective predetermined algorithm Ai;
controlling the generation of data items for at least one of the data streams DSi in dependence on the control data items of the control stream; and
forming the output stream by combining the generated data streams DSi.
The invention relates also to a computer program for performing the method and a computer-readable storage medium having the program recorded thereon.
Such a synchronous data-stream generator is known as the alternating step generator from xe2x80x9cHandbook of Applied Cryptographyxe2x80x9d, A. J. Menzes, P. C. van Oorschot, S. A. Vanstone, CRC Press, 1997, pages 209-211. In this system, two Linear Feedback Shift Registers (LFSRs) M1 and M2 are used to generate two data-streams. The data-streams are combined into one bit output stream of the data-stream generator via an XOR (Exclusive OR) operation. A third LFSR C is used as a control subgenerator whose output controls the clocking of the LFSRs M1 and M2. The sequence of operation is as follows:
register C is clocked
if the output of C is a logic xe2x80x9c1xe2x80x9d, then M1 is clocked; M2 is not clocked but its output is repeated
if the output of C is a logic xe2x80x9c0xe2x80x9d, then M2 is clocked; M1 is not clocked but its output is repeated
the outputs of M1 and M2 are combined.
Non-linearity is introduced in this system by using C to irregularly clock one of the subgenerators at a time under control of the output of the subgenerator C. The data stream generator can be used in many applications. For instance, the data-stream generator may be used as a pseudo-random generator, and as such can be used for encrypting/decrypting data by adding the output bits modulo 2 (XOR) to the data bits.
It is an object of the invention to provide a synchronous data-stream generator of the kind set forth which is more resistant against known attacks. It is a further object to provide such an improved data-stream generator that is suitable for use in digital consumer electronics systems with a low gate-complexity for a hardware implementation and offering a speed suitable for encryption/decryption of digital audio/video signals.
To meet the object of the invention, the control means comprises for at least one subgenerator Mi an associated number selector Si for, in dependence on the control data item of the control subgenerator C, selecting a number ni,j from a group Hi of different integer numbers; at least two numbers of the group Hi being larger than zero; the group Hi being associated with the number selector Si; and in that the control means is operative to cause the associated subgenerator Mi to provide at the output the selected ni,j-th data item successive to a last generated data item. In this way, the subgenerator(s) Mi is triggered/clocked more irregularly causing a higher level of non-linear behaviour. Instead of approximately half of the time the subgenerator not being clocked (i.e. maintaining the same output), the group may be larger with at least two integers being different from zero, allowing the subgenerator to be clocked more frequently (i.e. the output is less frequently kept constant which is the result of a xe2x80x98zeroxe2x80x99 being selected for the subgenerator and consequently the subgenerator not being clocked whereas another one is being clocked) and being provided with more than one trigger at a time (i.e. in fact skipping a number of ni,jxe2x88x921 data items and providing the ni,j-th data item at the output). Such a skipping may simply be performed by in response to one clock trigger to the data-stream generator, clocking a subgenerator ni,j times. By not or less frequently maintaining the same output of a subgenerator, the data stream generator has more states. The hardware/software required to achieve this can be kept to a minimum, making the improvements suitable for high-speed consumer electronic applications.
A data item may simply consist of one bit (0 or 1), or be formed using more bits, representing a larger range of numbers. Combining the output of the subgenerators may be done using a simple operation, such as a bitwise XOR, or may be a more complicated (non-)linear operation.
In an embodiment according to the measure as defined in the dependent claim 2, the balanced selection is an effective way to ensure maximum period.
According to the measure defined in the dependent claim 3, the subgenerator is always clocked at least once, ensuring that the combined output always contains a new contribution of each of the subgenerators. Selecting from two numbers, of which one number is a xe2x80x98onexe2x80x99 allows for a simple and fast implementation.
According to the measure defined in the dependent claim 4, at least two subgenerators are xe2x80x98irregularlyxe2x80x99 and differently clocked, increasing the non-linearity further.
According to the measure defined in the dependent claim 5, a finite state machine is used as a generator.
According to the measure defined in the dependent claim 6, a feedback shift register is used as the finite state machine, allowing a simple and fast implementation suitable for consumer electronic applications. The feedback shift register may have a linear feedback or, alternatively, a non-linear feedback.
According to the measure defined in the dependent claim 7, the ni,j-th output data item is generated in one operation (one trigger) instead of using ni,j successive clock triggers. In this way a high bit-rate can be achieved at an only marginal increase in gate-complexity. This makes the stream generator particularly suitable for use in digital audio/video equipment, such as a CD or DVD-like player, where a high bit-rate at low cost is required.
According to the measure defined in the dependent claim 8, more output bits of the control data item are used, increasing the variability in the number selection process.
Preferably, the data-stream generator is used in an encryptor and/or decryptor station for generating a pseudo-random stream of data items. Symmetrical encryption/decryption can then be achieved by combining (e.g. using an XOR operation) the generated data stream with a stream to be encrypted/decrypted. Advantageously, the decryptor is incorporated in a playback device, such as a disc player, where the data stream to be encrypted is read from a record carrier, such as a tape or disc. The encryptor and decryptor may also be used for protecting transfer of digital data, in particular audio and/or video data, via a network such as IEEE 1394. In such a case, raw digital data is encrypted in the transmitter station and decrypted in the receiving station. Key information may be provided in any suitable way, such as using public key exchange methods.
It is an object of the invention to provide a method for generating a synchronous data-stream, which is more resistant against known attacks. It is a further object to provide such method that is suitable for use in digital consumer electronics systems with a low gate-complexity for a hardware implementation and offering a speed suitable for encryption/decryption of digital audio/video signals.
To meet the object of the invention, the method is characterised in that the step of controlling the generation of data items for at least one of the data streams DSi comprises selecting for the data stream DSi a number n from an associated group of different integer numbers; at least two numbers of the groups being larger than zero; the selection being in dependence on the control data items of the control stream; and
the step of generating a data item for the data stream DSi comprises generating as a next data item of the data stream DSi a data item which according to the algorithm Ai would be the n-th data item successive to a last generated data item.
In this method, the algorithm Ai corresponds to the functionality of subgenerator M1 and as such will not be described in detail separately.
The invention also relates to computer program for causing a processor to perform this method. The program may be for any suitable processor, such as an embedded microcontroller or Risc-processor, or for processors optimized for executing encryption software. Implementing the steps of the method in software functions lies within the skills of a skilled person and will not be elaborated further.
The invention also relates to a computer-readable storage medium having the computer program. Any suitable medium may be used, like a magnetic storage medium (e.g. floppy disk), or optical storage medium, such as a CD-ROM, or electrical storage medium, such as (non-volatile) RAM or ROM.